package com.zjsru.oneDay202211;

/**
 * @Author: CookLee
 * @Date: 2022/11/27
 *
 * 检查数组是否经排序和轮转得到
 * 我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。
 *
 * 输入：nums = [3,4,5,1,2]
 * 输出：true
 * 解释：[1,2,3,4,5] 为有序的源数组。
 * 可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。】
 *
 * 输入：nums = [2,1,3,4]
 * 输出：false
 * 解释：源数组无法经轮转得到 nums 。
 *
 *
 */
public class Check {
    
    /**
     * 模拟 内存击败39.5% 时间100%
     */
    public boolean check(int[] nums) {
        //对数组进行复制， 长度为原数组的两倍
        int[] ints = new int[nums.length * 2];
        for (int i = 0, k = 0; i < ints.length; i++) {
            ints[i] = nums[k];
            k++;
            if (k == nums.length) {
                k = 0;
            }
        }
        //计数，如果前一个数字大于后一个字数 则代表原数组轮转不到该位置，cnt++
        int cnt = 0;
        for (int i = 1; i < ints.length; i++) {
            if (ints[i - 1] > ints[i]) {
                cnt++;
            }
        }
        //当cnt 大于2时，表示经过排序递增的数组轮转不到该位置。 示例：1234512345
        return cnt <= 2;
    }
    
    
    /**
     * 模拟,基于第一个方法的简化
     */
    public boolean check2(int[] nums) {
        int len = nums.length, cnt = 0;
        for (int i = 1; i < len; i++) {
            if (cnt > 1) {
                return false;
            }
            if (nums[i - 1] > nums[i]) {
                cnt++;
            }
        }
        // ans == 0 表示是一个递增数组 即移动0的情况
        // ans == 1 nums[0] > nums[len - 1] 表示在满足递增次数的同时要保证头尾数组是递增情况，若不是则代表数组不是递增顺序
        return (cnt == 0 || (cnt == 1 && nums[0] > nums[len - 1]));
    }
    
    /**
     * 按照题意给出的条件判断： A[i] == B[(i+x) % A.length]
     */
    public boolean check3(int[] nums) {
        int len = nums.length, cnt = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] > nums[(i + 1) % len]) {
                cnt++;
            }
            if (cnt > 1) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        Check check = new Check();
        int[] nums = new int[] {3, 4, 5, 1, 2};
        System.out.println(check.check(nums));
    }
}
